package com.zzs.astar;

import java.util.*;

public class Demo {
    // 地图元素
    public final static char START = 'S';
    public final static char END = 'E';
    public final static char SPACE = '.';
    public final static char WALL = 'W';
    public final static char VISITED = '+';
    public final static char PATH = '*';

    // 地图
    public static String[] s_map ={
            "....................",
            "....WWWW............",
            ".......W............",
            ".......W............",
            "...S...W............",
            ".......W............",
            ".......W............",
            ".......W............",
            "....WWWW............",
            ".................E..",
    };

    public static Entity START_ENTITY = null;
    public static Entity END_ENTITY = null;


    public static int row = 10;
    public static int col = 20;

    public static char[][] map;

    public static void main(String[] args) {
        getMap(); // 构建地图
        printMap();
        aStar();
        printMap();
    }



    public static boolean aStar(){
        Set<Node> close = new HashSet<>();
        List<Node> open = new ArrayList<>();
        Node lastNode = null; // close中最后一个加入的node节点
        final int[][] directs = { // 扩展的方向
                {1,0},  // 下
                {-1,0}, // 上
                {0,1}, // 右
                {0,-1} // 左
        };

        Node start = new Node(START_ENTITY,0,0,null); // 创建起点
        open.add(start);
        //lastNode = start;
        boolean finish = false;

        while(!finish && !open.isEmpty()){
            // 找到open中的f最小的node，从 open 移动到 close
            lastNode = getMinFromOpen(open);
            close.add(lastNode);

            for(int[] d: directs){ // 各个方向进行扩展
                int x = lastNode.entity.x + d[0];
                int y = lastNode.entity.y + d[1];
                if( x >= 0 && y>=0 && x<row && y<col ){
                    char e = map[x][y];
                    if(e == END){
                        finish = true;
                        break;
                    }
                    //if(e != SPACE){
                    //    continue;
                    //}

                    if(e == WALL){
                        continue;
                    }


                    // 创建这个节点
                    Node neighborNode = new Node(new Entity(x,y),lastNode.g+1, h(x,y), lastNode);
                    if(close.contains(neighborNode)){ // 如果在close中
                        continue;
                    }
                    // 修改标记为已探测
                    map[x][y] = VISITED;

                    Node other = getNodeFromOpen(open, neighborNode);
                    if(other != null){ // 如果在open中，判断是否有更近的路
                        if(lastNode.g + 1  < other.g){
                            other.g = lastNode.g + 1;
                            other.parent = lastNode;
                        }
                    }else{ // 如果不在open，则加入open
                        open.add(neighborNode);
                    }
                }
            }

        }

        if(finish){
            System.out.println("成功找到路径");
            // 根据lastNode反向获取路径
            while(!lastNode.entity.equals(START_ENTITY)){
                map[lastNode.entity.x][lastNode.entity.y] = PATH;
                lastNode = lastNode.parent;
            }
        }else{
            System.out.println("没有找到路径");
        }
        return finish;
    }

    /**
     * 从 open 列表中获取 节点
     * @param open
     * @param node
     * @return 获取该节点用于判断 g 是否合适，是否需要更新
     */
    public static Node getNodeFromOpen(List<Node> open, Node node){
        for(int i = 0;i<open.size();i++){
            if(open.get(i).equals(node)){
                return open.get(i);
            }
        }
        return null;
    }

    /**
     * 从 open 中找到 f 最小的，移除并返回
     */
    public static Node getMinFromOpen(List<Node> open){
        int f = Integer.MAX_VALUE;
        int index = -1;
        for(int i = 0;i<open.size();i++){
            Node temp = open.get(i);
            if(temp.f() < f){
                f = temp.f();
                index = i;
            }
        }
        return open.remove(index);
    }


    /**
     * 生成地图数据
     */
    public static void getMap(){
        map = new char[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                map[i][j] = s_map[i].charAt(j);
                if(map[i][j] == 'S'){
                    START_ENTITY = new Entity(i,j);
                }else if(map[i][j] == 'E'){
                    END_ENTITY = new Entity(i,j);
                }
            }
        }
    }

    /**
     * 打印地图
     */
    public static void printMap(){
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                System.out.printf("%c ", map[i][j]);
            }
            System.out.println();
        }
    }

    // 计算h，评估函数
    public static int h(int x,int y){
        //return hManhattanDistance(x, y);
        return hPowEuclidianDistance(x, y);
        //return hBFS(x, y);
    }

    /**
     * 曼哈顿距离,小于等于实际值
     */
    public static int hManhattanDistance(int x,int y)
    {
        return Math.abs(x - END_ENTITY.x) + Math.abs(y - END_ENTITY.y);
    }

    /**
     * 欧式距离平方,大于等于实际值
     */
    static int hPowEuclidianDistance(int x,int y)
    {
        return (int)(Math.pow(x - END_ENTITY.x, 2) + Math.pow(y - END_ENTITY.y, 2));
    }

    /**
     * BFS的h值,恒为0
     */
    static int hBFS(int x,int y)
    {
        return 0;
    }
}
